#ifndef __DOUBLELINKVOID_HPP_
#define __DOUBLELINKVOID_HPP_
#include <iostream>

template <typename T>
class DoubleLinkList
{
public:
    DoubleLinkList();

    // 插入
    void InsertTail(const T &element);
    void InsertHead(const T &element);

    // 中间插
    void InsertByIndex(int index, const T element);
    // 按位置删
    void RemoveByIndex(int index);
    // 按值删
    void RemoveByElement(const T &element);
    // void* 回调版本
    int Size()
    {
        return size;
    }

    // 查找
    T *back()
    {
        return &tail->data;
    }

    T *Head()
    {
        return &head->next->data;
    }

    ~DoubleLinkList();
    void show();

private:
    struct Node
    {
        Node(const T &data) : data(data), prev(nullptr), next(nullptr) {}
        T data;
        Node *next;
        Node *prev; // 前置指针
    };

    Node *head; // 头指针
    Node *tail; // 尾指针
    int size;
};

template <class T>
DoubleLinkList<T>::DoubleLinkList()
{
    head = new Node(0);
    tail = head;
    size = 0;
}

template <class T>
void DoubleLinkList<T>::InsertTail(const T &element)
{
    Node *newNode = new Node(element);
    tail->next = newNode;
    newNode->prev = tail;
    tail = newNode;
    size++;
}

template <class T>
void DoubleLinkList<T>::InsertHead(const T &element)
{
    Node *newNode = new Node(element);
    newNode->next = head->next;
    newNode->prev = head;
    head->next = newNode;
    if (size != 0)
        newNode->next->prev = newNode;
    else
        tail = newNode;
    size++;
}

template <class T>
void DoubleLinkList<T>::InsertByIndex(int index, T element)
{
    Node *travelPoint = head;
    for (int i = 0; i < index; i++)
    {
        travelPoint = travelPoint->next;
    }
    Node *newNode = new Node(element);
    newNode->next = travelPoint->next;
    newNode->prev = travelPoint;
    travelPoint->next = newNode;
    if (index != size)
        newNode->next->prev = newNode;
    else
        tail = newNode;

    size++;
}

template <class T>
void DoubleLinkList<T>::RemoveByIndex(int index)
{
    if (index < 0 || index >= size)
    {
        std::cout << "非法的删除位置" << std::endl;
        return;
    }
    Node *travelPoint = head;
    for (int i = 0; i < index; i++)
    {
        travelPoint = travelPoint->next;
    }
    Node *freeNode = travelPoint->next;

    if (freeNode->next != nullptr)
    {
        travelPoint->next = freeNode->next;
        freeNode->next->prev = travelPoint;
    }
    else
    {
        travelPoint->next = nullptr;
        tail = travelPoint;
    }
    delete freeNode;
    size--;
}

template <class T>
void DoubleLinkList<T>::RemoveByElement(const T &element)
{
    Node *travelPoint = head;
    while (travelPoint->next != nullptr)
    {
        if (travelPoint->next->data == element)
        {
            Node *freeNode = travelPoint->next;
            if (freeNode->next != nullptr)
            {
                travelPoint->next = freeNode->next;
                freeNode->next->prev = travelPoint;
            }
            else
            {
                travelPoint->next = nullptr;
                tail = travelPoint;
            }
            delete freeNode;
            size--;
        }
        else
            travelPoint = travelPoint->next;
    }
}

template <class T>
DoubleLinkList<T>::~DoubleLinkList()
{
    // 链表不能回头
    while (head != nullptr)
    {
        Node *nextNode = head->next; // 记下下一个节点
        delete head;
        head = nextNode; // 结点往后走
    }
}

template <class T>
void DoubleLinkList<T>::show()
{
    std::cout << "size:" << size << std::endl;
    // 遍历指针
    Node *travelPoint = head->next;
    while (travelPoint != nullptr)
    {
        std::cout << travelPoint->data << std::endl;
        travelPoint = travelPoint->next;
    }
    std::cout << std::endl;

    travelPoint = tail;
    while (travelPoint != head)
    {
        std::cout << travelPoint->data << std::endl;
        travelPoint = travelPoint->prev;
    }
    std::cout << std::endl;
}

#endif